#include <iostream>
#include <vector>

using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();

    if (m > n) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int left = 0;
    int right = m;
    int halfLength = (m + n + 1) / 2;

    while (left <= right) {
        int partitionX = left + (right - left) / 2;
        int partitionY = halfLength - partitionX;

        int maxLeftX = (partitionX == 0) ? INT32_MIN : nums1[partitionX - 1];
        int minRightX = (partitionX == m) ? INT32_MAX : nums1[partitionX];
        int maxLeftY = (partitionY == 0) ? INT32_MIN : nums2[partitionY - 1];
        int minRightY = (partitionY == n) ? INT32_MAX : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((m + n) % 2 == 0) {   
                return (static_cast<double>(max(maxLeftX, maxLeftY)) + min(minRightX, minRightY)) / 2.0;
            } else {  
                return max(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) { 
            right = partitionX - 1;
        } else {   
            left = partitionX + 1;
        }
    }

    throw runtime_error("输入的数组不是正序数组！");
}

int main() {
    vector<int> nums1 = {1, 3};
    vector<int> nums2 = {2};

    double median = findMedianSortedArrays(nums1, nums2);

    cout << "两个有序数组的中位数为：" << median << endl;

    return 0;
}